#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x), next(nullptr){}
};

class Solution{
    private:
    vector<pair<int, ListNode*>> map;

    public:
    ListNode* ans1(vector<ListNode*>& lists){
        int len = lists.size();
        for(int i = 0; i != len; i++){
            ListNode* temp_head = lists[i];
            while(temp_head != nullptr){
                map.push_back({temp_head->val, temp_head});
                temp_head = temp_head->next;
            }
        }

        sort(map.begin(), map.end());
        ListNode* ret, *tail;
        for(auto it = map.begin(); it != map.end(); it++){
            if(it == map.begin()){
                ret = tail = it->second;
            }else{
                tail->next = it->second;
                tail = tail->next;
            }
        }
        tail->next = nullptr;

        return ret;
    }

    ListNode* createList(vector<int>& nums){
        ListNode* head = new ListNode(nums[0]);
        ListNode* tail = head;
        for(int i = 1; i != nums.size(); i++){
            ListNode* temp = new ListNode(nums[i]);
            tail->next = temp;
            tail = temp;
        }
        return head;
    }

    void show(ListNode* root){
        ListNode* head = root;
        while(head != nullptr){
            cout << head->val << " " << ends;
            head = head->next;
        }
        cout << endl;
    }
};

void test(){
    Solution s;
    vector<vector<int>> nums = {
        {1,4,5},
        {1,3,4},
        {2,6}
    };
    int len = nums.size();
    vector<ListNode*> head;
    for(int i = 0; i != len; i++){
        head.push_back(s.createList(nums[i]));
    }

    ListNode* ret = s.ans1(head);
    s.show(ret);

}

int main(void){
    test();

    return 0;
}